package ink.lovejinhu.swardToOffer;

/**
 * @author jinhu
 * created 2021-08-17 15:52
 */
public class Offer_048 {
    /**
     * 最长不含重复字符的子字符串
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        /**
         * f(i)=f(i-1)||f(i-1)+1
         */
        int res = 1;
        int start = 0;
        int end = 0;
        for (int i = 1; i < s.length(); i++) {
            if (this.isContain(s, start, end, s.charAt(i)) != -1) {  //包含
                if (res < end - start + 1) {
                    res = end - start + 1;
                }
                start = this.isContain(s, start, end, s.charAt(i)) + 1;
                end = i;
            } else {
                end++;
            }

        }
        return Math.max(end - start + 1, res);
    }

    public int isContain(String s, int left, int right, char a) {
        for (int i = left; i <= right; i++) {
            if (s.charAt(i) == a) {
                return i;
            }

        }
        return -1;
    }
}
